#
# 09/10/11
# Implement prefix span algorithm to discover frequential pattern
# in an event squence
#
# Using data structures and algorithm from prefixspan.cpp
#
# Input format: Each line represents a event
#   10
#   20
#   30
#   10
#   20
#   30
#   20
#   10
#   20
#   10
#
# Output format: all frequential pattern, which has length*frequent > minsup
#
# frequent = number of sequence / N
# 
# For Ex: with minsup = 0.5
# Output:
#   10 20 30 (3 * 0.2 = 0.6)
#   10 20 (2 * 0.3 = 0.6)

import os
from collections import *
from optparse import OptionParser

class PrefixSpan:

    # Init
    def __init__(self, all = False, minsup = 1, minpat = 1, maxpat = 0xffffffff):
        
        # Store all the events_sequence
        self.events_sequence = []
        
        # Store the pattern
        self.pattern = []
        
        self.all = all
        
        # Value for discovering frequential pattern
        self.minsup = minsup
        self.minpat = minpat
        self.maxpat = maxpat
        
        # Output data
        self.output_data = ''
        
    # Read events_sequence from input file
    def read_data(self, filename):
        f = open(filename, "r")
        for line in f.readlines():
            if len(line) < 1: break
            self.events_sequence += [int(line)]
        f.close()
        
        # DEBUG
        print self.events_sequence
        
    # Write to output_data to output file
    def write_output(self, filename):
        f = open(filename, "w")
        f.write(self.output_data)
        f.close()    
        
    # Adding sequence to output_data
    def add_result(self, projected):
        # DEBUG
        #print "Pattern :", self.pattern
    
        if self.minpat > len(self.pattern): return
        
        if self.all:
            self.output_data += "%d" % self.pattern[-1][1]
            
            for i in range(len(self.pattern)):
                self.output_data += " %d" % self.pattern[i][0]
        else:
            for i in range(len(self.pattern)):
                tmp = "%d" % (self.pattern[i][0])
                if i != 0:
                    self.output_data += ' '
                self.output_data += tmp
        self.output_data += "\n"
        
    # Implement the prefix span algorithm
    def prefixspan(self, projected, init = False):
    
        # DEBUG
        print "projected : ", projected
        
        if (self.all): self.add_result(projected)
        
        counter = defaultdict(list)
        size = len(self.events_sequence)
        
        # Expand the pattern store in the projected
        for i in range(len(projected)):
            pos = projected[i]
            
            tmp = defaultdict(list)
            
            if (init):
                # Adding each of the item in the events_sequence id
                # into the tmp
                for j in range(pos+1, size):
                    item = self.events_sequence[j]
                    tmp[item] += [j]
            else:
                # Adding the item (pos + 1) in the events_sequence id
                j = pos + 1
                
                if (j < size):
                    item = self.events_sequence[j]
                    if item not in tmp: tmp[item] = [j]
            
            # DEBUG
            #print tmp
            
            for key in tmp:
                counter[key] += tmp[key]
                    
        # DEBUG
        #print counter
        
        # Update counter by erasing the un-interested pattern
        del_key = []
        for iter in counter:
            frequent = len(counter[iter])*1.0 / size
            if (frequent*(len(self.pattern)+1) < self.minsup):
                del_key += [iter]
                
        for key in del_key:
            del counter[key]
            
        # DEBUG
        #print counter
                        
        if (not self.all and len(counter) == 0):
            self.add_result(projected)
            return
        
        # Add new pattern and continue searching
        for iter in counter:
            if len(self.pattern) < self.maxpat:
                self.pattern += [(iter, len(counter[iter]))]
                self.prefixspan(counter[iter], init = False)
                del self.pattern[-1]
                
    # Running the prefix span algorithm
    def run(self):
        root = []
        root += [-1]

        # DEBUG
        #print root
        self.prefixspan(root, init = True)
        
# Main
if __name__=="__main__":
    parser = OptionParser()
    parser.add_option("-i", dest="input_file", default="data.in", type="string", help="events_sequence data", metavar="FILE")
    parser.add_option("-o", dest="output_file", default="data.out", type="string", help="mined sequential pattern", metavar="FILE")
    parser.add_option("-m", dest="minsup", default=1, type="float", help="min support value", metavar="int")
    parser.add_option("-a", dest="all", action="store_true", default = False)

    (options, args) = parser.parse_args()

    prefixspan = PrefixSpan(all = options.all, minsup = options.minsup)
    prefixspan.read_data(options.input_file)
    prefixspan.run()
    prefixspan.write_output(options.output_file)
